#include <stdio.h>
#include <stdlib.h>

struct list
	{
	
	int val;
	struct list *next;
	
	}*p;

void display()
	{
	
	struct list *t;
	t=p;
	
	printf("\n[");
	
	if(p==NULL)
		printf(" ");
	
	else
		{
		while(t->next!=NULL)
			{
			printf("%d, ", t->val);
			t=t->next;
			}
		printf("%d", t->val);
		}
	
	printf("]\n");
	
	}

void append(int n)
	{
	
	struct list *t, *new;
	
	int i;
	
	for(i=0; i<n; i++)
		{
		
		t=p;
		
		new=malloc(sizeof(struct list));
		
		printf("\nEnter element: ");
		scanf("%d", &(new->val));
		
		if(p==NULL)
			p=new;
		else
			{
			while(t->next!=NULL)
				t=t->next;
			t->next=new;
			}
		
		}
		
	}

void insert()
	{
	
	if(p==NULL)
		{
		printf("\nList is empty. Element will be inserted in position 0.\n");
		append(1);
		return;
		}
	
	struct list *t1, *t2, *new;
	
	int pos;
	
	int i=0;
	
	new=malloc(sizeof(struct list));
	
	t1=p;
	t2=p->next;
	
	printf("\nEnter element: ");
	scanf("%d", &(new->val));
	
	printf("\nEnter position: ");
	scanf("%d", &pos);
	
	if(pos<0)
		{
		printf("\nPosition entered is less than 0. Element will be inserted at beginning of list.\n");
		new->next=p;
		p=new;
		return;
		}
	
	if(pos==0)
		{
		new->next=p;
		p=new;
		return;
		}
	
	while((t1!=NULL)&&(i<pos))
		{
		
		if(i+1==pos)
			{
			new->next=t2;
			t1->next=new;
			return;
			}
		else
			{
			t1=t1->next;
			t2=t2->next;
			i++;
			}
		
		}
	
	}

void myremove()
	{
	
	if(p==NULL)
		{
		printf("\nList is empty.\n");
		return;
		}
	
	struct list *t1, *t2;
	
	int num;
	
	t1=p;
	t2=p->next;
	
	printf("\nEnter the element to be removed: ");
	scanf("%d", &num);
	
	if(p->val==num)
		{
		p=p->next;
		free(t1);
		printf("\nElement found and removed.\n");
		return;
		}
	
	while((t1!=NULL)&&(t2!=NULL))
		{
		if(t2->val==num)
			{
			t1->next=t2->next;
			free(t2);
			printf("\nElement found and removed.\n");
			return;
			}
		else
			{
			t1=t1->next;
			t2=t2->next;
			}
		}
	
	printf("\nElement not found.\n");
	
	}

void pop()
	{
	
	if(p==NULL)
		{
		printf("\nList is empty.\n");
		return;
		}
	
	struct list *t1, *t2;
	
	int pos;
	
	int i=0;
	
	t1=p;
	t2=p->next;
	
	printf("\nEnter position of element to be popped: ");
	scanf("%d", &pos);
	
	if(pos==0)
		{
		p=p->next;
		printf("\nPopped element: %d\n", t1->val);
		free(t1);
		return;
		}
	
	while((t1!=NULL)&&(t2!=NULL)&&(i<pos))
		{
		if(i+1==pos)
			{
			printf("\nPopped element: %d\n", t2->val);
			t1->next=t2->next;
			free(t2);
			return;
			}
		else
			{
			t1=t1->next;
			t2=t2->next;
			i++;
			}
		}
	
	printf("\nElement was not popped.\n");
	
	}

void count()
	{
	
	if(p==NULL)
		{
		printf("\nList is empty.\n");
		return;
		}
	
	int num;
	
	int count=0;
	
	struct list *t;
	
	t=p;
	
	printf("\nEnter element to be counted: ");
	scanf("%d", &num);
	
	while(t!=NULL)
		{
		if(t->val==num)
			count++;
		t=t->next;
		}
	
	printf("\nNumber of times %d occurred: %d\n", num, count);
	
	}

void myindex()
	{
	
	if(p==NULL)
		{
		printf("\nList is empty.\n");
		return;
		}
	
	int num;
	
	int pos=0;
	
	struct list *t;
	
	t=p;
	
	printf("\nEnter element whose index is to be found: ");
	scanf("%d", &num);
	
	while(t!=NULL)
		{
		
		if(t->val==num)
			{
			printf("\nElement %d found at position: %d\n", num, pos);
			return;
			}
		
		t=t->next;
		pos++;
		
		}
	
	printf("\nElement not found.\n");
	
	}

void reverse()
	{
	
	printf("\nReversed list:\n");
	
	if(p==NULL)
		{
		display();
		return;
		}
	
	if(p->next==NULL)
		{
		display();
		return;
		}
	
	struct list *a, *b, *original;
	
	original=a=b=p;
	
	while(a->next!=NULL)
		a=a->next;
	
	p=a;
	
	while(a->next!=original)
		{
		
		b=original;
		while(b->next!=a)
			b=b->next;
		a->next=b;
		a=a->next;
		
		}
	
	original->next=NULL;
	
	display();
	
	}

void sort()
	{
	
	printf("\nSorted list:\n");
	
	if(p==NULL)
		{
		display();
		return;
		}
	
	if(p->next==NULL)
		{
		display();
		return;
		}
	
	struct list *t1, *t2;
	
	t1=p;
	
	while(t1!=NULL)
		{
		
		t2=t1->next;
		
		while(t2!=NULL)
			{
			
			if(t1->val>t2->val)
				{
				t1->val=t1->val+t2->val;
				t2->val=t1->val-t2->val;
				t1->val=t1->val-t2->val;
				}
			
			t2=t2->next;
			
			}
		
		t1=t1->next;
		
		}
	
	display();
	
	}

void main()
{

int choice;

int append_no;

p=NULL;

while(1)
	{
	
	printf("\nMenu\n\n1. Display\n2. Insert\n3. Append\n4. Extend\n5. Remove\n6. Pop\n7. Count\n8. Index\n9. Reverse\n10. Sort\n11. Exit");
	printf("\n\nEnter your choice: ");
	scanf("%d", &choice);
	
	switch(choice)
		{
		
		case 1:
			display();
			break;
		
		case 2:
			insert();
			break;
		
		case 3:
			append(1);
			break;
		
		case 4:
			printf("\nEnter no. of elements: ");
			scanf("%d", &append_no);
			append(append_no);
			break;
		
		case 5:
			myremove();
			break;
		
		case 6:
			pop();
			break;
		
		case 7:
			count();
			break;
		
		case 8:
			myindex();
			break;
		
		case 9:
			reverse();
			break;
		
		case 10:
			sort();
			break;
		
		case 11:
			printf("\n");
			exit(0);
		
		default:
			printf("\nInvalid option.");
		
		}
	
	}

}
